In recent years, storage apparatuses (storage devices) each including a solid state drive (SSD) appear. The SSD is constructed from a rewritable non-volatile memory. A flash memory is generally used as the rewritable non-volatile memory. Since the SSD does not require mechanical control accompanying rotation of a disk, it is possible to access the SSD at a high speed as compared with a hard disk drive (HDD) using a magnetic disk.
However, to write to the SSD (more specifically, flash memory in SSD), some restrictions are imposed unlike writing to the HDD. Firstly, when data which is already written to the SSD is to be rewritten, there is required a procedure to erase the data (i.e., existing old data) and then to write new data. To erase data, it is only possible to execute the erasing in units called blocks (memory block or physical block) of about several hundred kilobytes (KB).
Hence, the SSD is generally configured using a flash memory having a capacity larger than a capacity of a storage device required (or recognized) by a host computer (hereinafter, referred to as a host) utilizing the SSD. A storage device including a plurality of SSDs defines (constructs) a plurality of logical units (logical disks) by selectively allocating a plurality of physical blocks to the plurality of logical units. The plurality of physical blocks are obtained by partitioning a storage area of each of the SSDs into predetermined capacities (sizes). The host reads and writes data from and to the logical units. The SSD is called a physical memory or a physical disk. A logical address is used when the logical unit is accessed from the host, and a physical address is used when the physical memory accessed. Generally, the logical address is not equal to the physical address. Even if the logical address is equal to the physical address in an initial state, when rewriting of data in the logical unit (i.e., rewriting of data in physical memory) is repeated, the logical address becomes different from the physical address.
The host accesses the physical memory (SSD) by logically accessing the logical unit using the logical address. To make it possible for the host to access, for example, a controller incorporated in the SSD manages a corresponding relation between the logical address and the physical address.
It is assumed that the storage device is in its initial state where the logical address and the physical address are equal to each other. It is assumed that in this state, data having a size smaller than a block size is written to the logical unit. In this case, the SSD does not write data to the physical block that is allocated to the logical address where the writing is executed, and does not update the data. Instead of updating the data, old data before it is updated is managed as invalid. On the other hand, the SSD newly allocates an unused physical block to the logical address, and data is written to this newly allocated physical block.
Generation of an area of invalidated data in the SSD is called fragmentation of a memory area (more specifically, effective memory area). It is assumed that fragmentation of the memory area proceeds, and the blocks (more specifically, blocks in use) including the invalidated data areas increase. In this case, since free blocks (unused physical blocks) that can be used in the SSD (physical memory) are reduced, it becomes impossible to write new data. Hence, the SSD autonomously lumps together and rewrites effective data recorded in a plurality of physical blocks including the invalidated data to an unused physical block. Then, the SSD erases data in the plurality of physical blocks that become unnecessary by the rewriting. Such a process is called a defragmentation process. By the defragmentation process, the plurality of the physical blocks can be re-used as unused blocks (free blocks).
However, a frequency of execution of the defragmentation process becomes high in the SSD, and an access speed of the SSD lowers.
Hence, it is required to reduce the frequency of the execution of the defragmentation process in the SSD.